package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-19 10:49
 */
public class BuyAndSellStock {
    public static void main(String[] args) {

    }

    /**LeetCode 198
     * 思路：每一天最大的持有现金的数量与前一天的持有现金的数量及买卖状态相关，所以我们的实现思路是从前往后进行递推
     * 五部曲：1.dp[i][0]:第i天的持有股票手中有的现金数量  dp[i][1]代表的是第i天手中有股票手中现金的最大数量
     * 2.递推公式：dp[i][0]=max(dp[i-1][0],-prices) dp[i][1]=max(dp[i-1][1],dp[i-1][0]+price[i])
     * 3.初始化：dp[0][0]=-price[0] dp[0][1]=0 4.遍历顺序：从前往后遍历
     * @param nums
     * @return
     */
    public static int maxMoney(int[]nums){
        //创建dp数组
        int[][]dp=new int[nums.length][2];
        dp[0][0]=-nums[0];
        dp[0][1]=0;
        for(int i=1;i< nums.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],-nums[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+nums[i]);
        }
        //返回最后一天手中没有股票的数量
        return dp[nums.length][1];
    }
}
